package ljl.alg.wangzheng_camp.round1.find_the_law;

/**
 * 这个题我上次就没做出来
 * 这是第三次了，应该还是做不出来
 *
 * 我知道很简单，虽然
 *
 * 没那么简单...
 *
 * 官方题解有两种，左程云一种，共三种解法
 *
 * */
public class _48_rotate {
    
    /**
     * 左神解法
     *
     * 记录左上右下两个点，使用四个变量
     * 转着圈复制
     * 每圈复制时，是一个点一个点直接拷贝到目标地点，循环 边长 - 1 次
     * 复制完一圈，往里缩一圈
     *
     * 好消息是，背过了...
     * 坏消息是，背过了
     *
     * */
    public void rotate1(int[][] matrix) {
        int left = 0, right = matrix[0].length - 1;
        int top = 0, down = matrix.length - 1;
        while (left < right) {
            copy(matrix, left++, right--, top++, down--);
        }
    }
    
    void copy(int[][] matrix, int left, int right, int top, int down) {
        int len = right - left;
        // 难的就是这个拷贝，不是很好想
        /*
        * 1 2 3
        * 4 5 6
        * 7 8 9
        *
        * 1 2 3 会跑到 3 6 9 那
        * */
        for (int i = 0; i < len; i++) {
            int t = matrix[top][left + i];
            matrix[top][left + i] = matrix[down - i][left];
            matrix[down - i][left] = matrix[down][right - i];
            matrix[down][right - i] = matrix[top + i][right];
            matrix[top + i][right] = t;
        }
    }
    
    /**
     * 这招需要你比较聪明
     * 就算不聪明，也要比较勤奋
     *
     * 先上下翻转，再延对角线翻转，就是结果
     * 不知道为什么，不过就是这样
     *
     * 比较快
     * */
    public void rotate2(int[][] matrix) {
        int n = matrix.length;
        // 上下！
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                swap(matrix, i, j, n - i - 1, j);
            }
        }
        // 斜歪着！
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                swap(matrix, i, j, j, i);
            }
        }
    }
    void swap(int[][] matrix, int i1, int j1, int i2, int j2) {
        int t = matrix[i1][j1];
        matrix[i1][j1] = matrix[i2][j2];
        matrix[i2][j2] = t;
    }
    
    /**
     * 这个也是官方题解，这个就不太好想了
     *
     * 这个解法太学术、太令人讨厌了
     *
     * 好好想吧，想明白了也不亏，补补数学
     *
     * 这个太难想了兄弟
     * 不但公式推导难想，连循环次数都很难想，起码我感觉很难，非常的难
     *
     * n 偶数，那横竖都是 n/2 次
     * n 奇数，最中间多一个点不需要旋转，
     * x 少一半被旋转，y 一半多点被旋转
     * 这就解释了 i 和 j 的取值范围
     *
     * 当把一个点 i,j 翻转后会到达坐标 j, n - 1 - i，设为公式 1
     * matrix[j, n - 1 - i] = matrix[i][j]
     *
     * 然后 i = j, j = n - 1 - i 代进公式 1
     * matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
     *
     * 然后 i = n - 1 - i, j = n - 1 - j 继续带入公式 1，别乱代
     * matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
     *      我代这一步的时候，不知道咋了
     *      n - 1 - i，然后 i = n - 1 - i
     *      我感觉两个 n - 1 - i 消了，最后等于零
     *      请问小李认为的对吗？
     *
     * 然后 i = n - 1 - j, j = i 继续带入公式 1
     * matrix[i][j] = matrix[n - 1 - j][i]
     *      不知道为什么，回来了
     *      到底是什么原因导致它回来了？
     *
     * 然后把你推导的这几个公式，连起来，用一个 t 防止覆盖就过了
     *
     *
     *
     * 操你妈搁这考数学呢？
     *
     * 比如边长为 5，0,2 -> 2,n-1
     *
     * 这个题你首先需要熟练的利用一个辅助矩阵来翻转
     * 还不会爬就想灌篮？
     *
     *
     * */
    public void rotate3(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}
